The present invention relates to wireless mesh networks. In particular, the invention relates to a wireless mesh network in which nodes in the network locally determine scheduling of messages based upon unmet message demand.
In wireless mesh network systems designed for low power, sensor/actuator-based applications, many devices in the network must be powered by long-life batteries or by low power energy-scavenging power sources. Power outlets, such as 120 VAC utilities, are typically not located nearby or may not be allowed into the hazardous areas where the instrumentation (sensors) and actuators must be located without incurring great installation expense. The need for low installation cost drives the need for battery-powered devices communicating as part of a wireless mesh network. Effective utilization of a limited power source, such as a primary cell battery which cannot be recharged, is vital for a well functioning wireless device. Batteries are expected to last more than 5 years and preferably as long as the life of the product.
In a true wireless mesh network, each device must be capable of routing messages for itself as well as other devices in the mesh network. The concept of messages hopping from node to node through the network is beneficial because lower power RF radios can be used, and yet the mesh network can span a significant physical area delivering messages from one end to the other. High power radios are not needed in a mesh network, in contrast a point-to-point system which employs remote devices talking directly to a centralized base-station.
A mesh network protocol allows for the formation of alternate paths for messaging between devices and between devices and a data collector, or a bridge or gateway to some higher level higher-speed data bus. Having alternate, redundant paths for wireless messages enhances data reliability by ensuring there is at least one alternate path for messages to flow even if another path gets blocked or degrades due to environmental influences or due to interference.
Some mesh network protocols are deterministically routed such that every device has an assigned parent and at least one alternate parent. In the hierarchy of the mesh network, much as in a human family, parents have children, children have grandchildren, and so on. Each device (or “node”) relays the messages for their descendants through the network to some final destination such as a gateway. The parenting devices may be battery-powered or limited-energy powered devices. The more descendants a node has, the more traffic it must route, which in turn directly increases its own power consumption and diminishes its battery life.
In order to save power, some protocols limit the amount of traffic any node can handle during any period of time by only turning on the radios of the nodes for limited amounts of time to listen for messages. Thus, to reduce average power, the protocol may allow duty-cycling of the radios between On and Off states. Some protocols use a global duty cycle to save power such that the entire network is On and Off at the same time. Other protocols (e.g. TDMA-based) use a local duty cycle where only the communicating pair of nodes that are linked together are scheduled to turn On and Off in a synchronized fashion at predetermined times. Typically, the link is pre-determined by assigning the pair of nodes a specific time slot for communications, an RF frequency channel to be used by the radios, who is to be receiving (Rx), and who is to be transmitting (Tx) at that moment in time.
Some protocols employ the concept of assigning links to nodes on a regular repetitive schedule and thereby enable regular delivery of updates and messages from devices in the network. Some advanced TMDA-based protocols may employ the concept of multiple active schedules, these multiple schedules running all at the same time or with certain schedules activated/deactivated by a global network controller as the need arises. For example, slow active schedules link nodes sending messages with longer periods of time (long cycle time) between messages to achieve low power consumption. Fast active schedules link nodes sending messages more rapidly for better throughput and lower latency, but result in higher power consumption in the nodes. With protocols that allow multiple active schedules, some schedules could be optimized for upstream traffic, others for downstream traffic and yet others for network management functions such as device joining and configuration. Globally activating/deactivating various schedules throughout the entire network in order to meet different needs at different times provides a modicum of flexibility for achieving advantageous trade-offs between power consumption and low latency, but applies the same schedule to all nodes and thus does not provide local optimization.
In a synchronized system, nodes will have to wait to transmit until their next predetermined On time before they can pass messages. Waiting increases latency, which can be very detrimental in many applications if not bounded and managed properly. If the pair of nodes that are linked together are not synchronized properly, they will not succeed in passing messages because the radios will be On at the wrong time or in the wrong mode (Rx or Tx) at the wrong time. If the only active schedule has a long cycle time, the time between scheduled links will be long and latency will suffer. If a fast schedule is activated, the time between scheduled links will be short but battery life will be measurably reduced over time.
Some protocols allow running a slow global schedule in the background and globally activating/deactivating an additional fast schedule. Since it takes time to globally activate a fast schedule throughout the entire network and get confirmation back from all nodes that they have heard the global command, the network or sub-network remains in the less responsive mode during the transition time. Furthermore, with a globally activated fast schedule, power is wasted in all the parenting nodes in the network, even those whose descendants will not benefit from the fast schedule. These unappreciative parent nodes must listen more often on the global fast active schedule (i.e. turn their radios On to Rx more often); even though their descendants have nothing extra to send that a regular active schedule would not suffice in that portion of the network.
Some protocols may limit the number of descendants a node can have, thereby reducing the load the node must support. Other protocols may employ a combination of all of these measures to reduce average power consumption. All of these power-saving measures have the effect of reducing the availability of the nodes in the network to do the work of passing messages, thereby increasing the latency of messages delivered through the network. Duty-cycling the radio increases latency. Hopping messages from node to node increases latency. Increasing hop depth (hop count) by limiting the number of descendants increases latency. Running a slow active schedule (long cycle period) increases latency. Even globally activating a fast active schedule takes time. It is likely that the value of information diminishes with time, so the longer the latency, the less valuable the information may be.
Improvements to the protocol to reduce the trade-off between power consumption and latency are very valuable, because they allow the same protocol to be used for a wide variety of end applications without user intervention and configuration. Improvements that provide local optimizations over global optimization are the most flexible and most valuable.